package cc.wsyw126.java.lintCode;

public class MaxArea {

    public static void main(String[] args) {
        int[][] maxarea = {{1, 0, 0, 0, 1}, {1, 1, 0, 0, 1}, {1, 0, 0, 0, 0}, {1, 0, 0, 1, 1}};
        int res = 0;
        int row = maxarea.length, column = maxarea[0].length;
        int[][] left = new int[row][column];
        int[][] up = new int[row][column];
        int[][] mark = new int[row][column];

        for (int i = 0; i < column; i++)
            if (maxarea[0][i] == 1) {
                left[0][i] = 1;
                up[0][i] = 1;
                mark[0][i] = 1;
            }
        for (int j = 1; j < row; j++)
            if (maxarea[j][0] == 1) {
                left[j][0] = 1;
                up[j][0] = 1;
                mark[j][0] = 1;
            }
        for (int i = 1; i < row; i++)
            for (int j = 1; j < column; j++) {
                if (maxarea[i][j] == 1) {
                    left[i][j] = left[i][j - 1] + 1;
                    up[i][j] = up[i - 1][j] + 1;
                    mark[i][j] = Math.min(left[i][j], up[i][j]);
                    if (mark[i][j] > mark[i - 1][j - 1]) mark[i][j] = mark[i - 1][j - 1] + 1;
                }
            }
        for (int i = 1; i < row; i++)
            for (int j = 1; j < column; j++)
                if (res < mark[i][j]) res = mark[i][j];
        System.out.print(res);
    }

}
